package stack_queue_true_023;

public class 关于二叉树操作的类但不是二叉树 {
    // 通过一棵树的根结点，来逻辑上表示一棵树
    public static TreeNode 手动构建二叉树() {
        TreeNode a = new TreeNode('A'); // 'A' 是 char 类型，char -> int 类型，就是这个字符的 unicode 编码（ascii 是 unicode 编码的子集）
        TreeNode b = new TreeNode('B');
        TreeNode c = new TreeNode('C');
        TreeNode d = new TreeNode('D');
        TreeNode e = new TreeNode('E');
        TreeNode f = new TreeNode('F');
        TreeNode g = new TreeNode('G');
        TreeNode h = new TreeNode('H');

        // 手动构建其关系
        a.left = b; a.right = c;
        b.left = d; b.right = e;
        c.left = f; c.right = g;
        d.left = null; d.right = null;  // 这行可以省略
        e.left = null; e.right = h;
        f.left = null; f.right = null;
        g.left = null; g.right = null;
        h.left = null; h.right = null;

        // 返回根结点即可
        return a;
    }

    public static void main2(String[] args) {
        TreeNode root = 手动构建二叉树();
        count = 0;
        countNode(root);    // count++ 了 8 次
        System.out.println("结点个数: " + count);


        count = 0;
        countNode(root);    // count++ 了 8 次
        System.out.println("结点个数: " + count);


        count = 0;
        countNode(root);    // count++ 了 8 次
        System.out.println("结点个数: " + count);
    }

    public static void main1(String[] args) {
        TreeNode root = 手动构建二叉树();
        // 传入要进行遍历的树的根结点，代表整棵树
//        preorder(root);

        // count 的生命周期是跨方法调用存在的
        // 这个时候 count == 0
        countNode(root);    // count++ 了 8 次
        // 这个时候 count == 8
        System.out.println("结点个数: " + count);   // 8

        // 这个时候 count == 8
        countNode(root);    // count++ 了 8 次
        // 这个时候 count == 8 + 8 == 16
        System.out.println("结点个数: " + count);   // 期望是 8

        // 这个时候 count == 16
        countNode(root);    // count++ 了 8 次
        // 这个时候 count == 16 + 8 == 24
        System.out.println("结点个数: " + count);   // 期望是 8
    }

    static int count;

    private static void countNode(TreeNode root) {
        if (root == null) {
            // root 为 null 的情况我不统计
            return;
        }

        // 去掉根的打印，替换成，没经过这里一次，记录 1 次
        count++;    // count 的生命周期需要跨方法存在（方法结束生命周期也需要存在）
        // 变量：对一块内存空间的抽象
        // 变量的生命周期：这块内存空间能生存多久
        // 不能使用局部变量：局部变量的生命周期是随着方法执行而存在；方法开始执行时，在 JVM 栈中分配内存（栈帧）；方法执行结束，栈帧消亡（内存被回收）
        // 当前，使用静态属性是比较方便的
        countNode(root.left);
        countNode(root.right);
    }

    // 参数：要遍历的树的根结点（注意，要遍历的树可能是空树：root 可能是 null
    // 经过树的结点时，打印结点中的元素即可
    private static void preorder(TreeNode root) {
        // 如果一棵树是空树，则其前序遍历是？
        // 空树的前序遍历，什么都不做
        // 当根结点是 null 时，直接含义：根结点不存在；间接含义：树的空树
        if (root == null) {
            // 代表要遍历的树是空树
            return;
        }

        // 说明这棵树不是空树
        // 1) 先处理根结点：当下的意义：打印当前结点中的元素
        System.out.printf("%s\n", root.toString());
        // 2) 采用相同的方式进行左子树的处理
        // 什么叫做采用相同的方式？ 递归调用 preorder() 方法
        // 应该传入的实参是什么？需要传入左子树 -> 左子树的根结点 -> 当前根结点的左孩子结点 -> root.left
        preorder(root.left);

        // 3) 采用相同的方式进行右子树的处理
        preorder(root.right);
    }

    private static void inorder(TreeNode root) {
        if (root == null) {
            return;
        }

        inorder(root.left);
        System.out.println(root.toString());
        inorder(root.right);
    }

    public static void main3(String[] args) {
        TreeNode root = 手动构建二叉树();
        postorder(root);
    }

    public static void postorder(TreeNode root) {
        if (root == null) {
            return;
        }

        // 第一次：从根过来
        postorder(root.left);
        // 第二次：从左子树回来
        postorder(root.right);
        // 第三次：从右子树回来
        System.out.println(root.toString());
    }

    // 使用聚合的思想统计结点的个数
    public static int getNodeSize(TreeNode root) {
        if (root == null) {
            // 空树
            return 0;   // 空树中没有结点
        }

        // 统计两个子树分别的结点个数，先左、先右都可以，一般先左
        int leftTreeNodeSize = getNodeSize(root.left);  // 传入的是左子树的根 root.left
        int rightTreeNodeSize = getNodeSize(root.right);

        // 进行汇总聚合
        // 最终的结点个数 = 左子树的结点个数 + 右子树的结点个数 + 1
        return leftTreeNodeSize + rightTreeNodeSize + 1;
    }

    public static void main4(String[] args) {
        TreeNode root = 手动构建二叉树();

        int size = getNodeSize(root);
        System.out.println(size);

        size = getNodeSize(root);
        System.out.println(size);

        size = getNodeSize(root);
        System.out.println(size);

        size = getNodeSize(root);
        System.out.println(size);
    }

    // 建议下来单步调试看看
    public static int getLeafNodeSize(TreeNode root) {
        if (root == null) {
            // 空树
            // 空树中一个结点都没有，自然叶子结点的个数就是 0 个
            return 0;
        }

        // root 是一棵树的根结点的身份出席的
        if (root.left == null && root.right == null) {
            // 根的左孩子不存在 && 根的右孩子不存在
            // 说明以这个 root 为根的树只有一个结点
            // 只有一个结点的树，这个根结点就是唯一的叶子结点，所以，叶子结点个数就是 1 个
            return 1;
        }

        // 走聚合汇总的思想
        int leftSize = getLeafNodeSize(root.left);
        int rightSize = getLeafNodeSize(root.right);

        return leftSize + rightSize;
    }

    public static void main5(String[] args) {
        TreeNode root = 手动构建二叉树();
        int size = getLeafNodeSize(root);
        System.out.println(size);
    }

    static int leafCount;
    // 遍历的思想查看二叉树中的结点个数
    // 先写个遍历过程（前序、中序、后序、层序）
    public static void preorderCountLeafNode(TreeNode root) {
        if (root == null) {
            return;
        }

        // 先处理根
        // 这时，我们不把 root 看作代表一棵树的根结点，而仅仅当成遍历时经过的某个结点
        // 就检查该结点是不是叶子结点
        // 因为无论何种遍历方式，树中的每个结点都要经过一次，意味这个结点都要检查是不是叶子结点
        // 什么叫做叶子结点，这个结点的左孩子和有孩子都不存在（都是 null）
        if (root.left == null && root.right == null) {
            // 说明 root 是一个叶子结点
            leafCount++;    // leafCount 的生命周期也得超越方法
        }
        preorderCountLeafNode(root.left);
        preorderCountLeafNode(root.right);
    }


    public static void main(String[] args) {
        TreeNode root = 手动构建二叉树();

        leafCount = 0;
        preorderCountLeafNode(root);
        System.out.println(leafCount);

        leafCount = 0;
        preorderCountLeafNode(root);
        System.out.println(leafCount);

        leafCount = 0;
        preorderCountLeafNode(root);
        System.out.println(leafCount);
    }
}
